KURZUS: Alkalmazott operációkutatás

MODUL: II. modul: Egészértékű programozási feladat fogalma és grafikus megoldása. Néhány nevezetes egészértékű modell

8. lecke: Többcélú lineáris programozás

|  | Tanulási útmutató
| A többcélú lineáris programozás fogalma, grafikus szemléltetése és szimplex módszerrel történő megoldása a tankönyv 6. fejezetében található.
| Pareto-optimális megoldás fogalmát a tankönyvben olvashatja. Fontos, hogy a fogalmakat jól megértse, mert a gyakorlatban gyakran található olyan gazdasági probléma, amely igényli, hogy több cél figyelembevételével oldjuk meg. Ha találunk olyan megoldást, amely két vagy több célfüggvénynek is optimális megoldása, akkor nincs igazán számunkra tennivaló, hiszen találtunk közös optimális megoldást.
| Ha nincs olyan megoldás, amely minden célfüggvény szerint optimális, akkor ún. "kompromisszumos" megoldást keresünk. Különösen jól alkalmazhatók számunkra a felsorolt módszerek, mert a Solver program segítségével ezek könnyen megvalósíthatók és lefuttathatók.
| Tevékenységek
| Figyelmesen olvassa el a tankönyvben található definíciót és jól jegyezze meg a matematikai modelljét.
| Kövesse végig a 6. fejezetben található táblázatban a számítást. Figyelje a célfüggvények sorát és láthatja, hogy mikor az első, mikor a másik célfüggvény szerint optimális. Itt a B3 táblázatban jól nyomon követhető Pareto-elv.
| A kompromisszumos megoldás 1. esete.
| Ezt akkor alkalmazhatja, ha számítógéppel előállította az egyik célfüggvény szerinti optimális megoldást, majd a többi célfüggvény szerinti optimális megoldásokat. A célfüggvények súlyának ismeretében előállíthatja a célnak megfelelő kompromisszumos megoldást. Ezt Solver segítségével úgy valósíthatja meg, hogy a célfüggvények képleteit egymás alatti cellában helyezi el és megoldja a feladatot az egyik, majd a másik célfüggvény szerint. Utána vegye a két optimális megoldás konvex lineáris kombinációját!
| Korlátok módszere
| Ha már tudja, hogy nincs közös optimális megoldás, akkor alkalmazza a korlátok módszerét. Ha ismeretünk van arról, hogy milyen valós alsókorlátot tudunk adni a második célfüggvénynek, akkor a Solver programmal a megoldás csak annyi, hogy a korlátozó feltételekhez felvesszük az új egyenletünk bal oldalát ≥ jel alkalmazásával és lefuttatjuk az első célfüggvényt figyelembevételével a programot.
| A legkisebb célfüggvény értékének maximalizálása:
| A tankönyvben található bemutató feladatnál látható módon kell a Solver segítségével megoldani, azaz az eredeti Excel-táblázatot ki kell egészíteni egy új oszloppal és két új sorral. A célfüggvény helye és értéke az y változó cellája lehet.
| Követelmények
| Kulcsszavak kiválasztásával ki tudja egészíteni a több célú programozás és a Paretó-optimum fogalmára vonatkozó mondatokat.
| Felsorolásból ki tudja választani a "kompromisszumos" megoldás eseteit.
| Szimplex táblázatról le tudja olvasni, illetve az alapján elő tudja állítani a kétcélú lineáris programozási feladat megoldásait!
| Solver segítségével meg tud oldani olyan kétcélú lineáris programozási feladatot, amelyben valamely kompromisszumot alkalmazz!

|  | Bemutató feladat
| Oldja meg Solver segítségével a következő többcélú programozási feladatot a célfüggvények súlyozási módszerével!
| x 1 +2 x 2 ≤ 80 x 1 + x 2 ≤ 60 x 2 ≤ 30 z 1 =2 x 1 +4 x 2 → max⁡ z 2 = x 1 + x 2 → max⁡
| Az első célfüggvény súlya 70%, a második célfüggvény súlya pedig 30% legyen.
| Az adatokat már a tanult módon vigyük be az Excelbe.
| Korlátozó feltételek (egyenként kell felvenni őket):
| $D$3<=$F$3 $D$4<=$F$4 $D$5<=$F$5

|  | Önellenőrző feladatok
| 1. Fogalmazza meg az alábbi kulcsszavak felhasználásával a többcélú programozási feladatok megoldása során felhasznált módszereket:
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
alsó | célfüggvény | felső | első | második | y | szorzom | összeadom
| 1/a Írja be a fenti számokat a megfelelő helyre! Korlátok módszerének lényege: A(z) célfüggvényt bevisszük a feltételek közé valamilyen korláttal és megoldjuk a feladatot a(z) célfüggvény szerint. A legkisebb célfüggvény értékének maximalizálása: Mindegyik -t bevisszük a korlátozó feltételek közé egy alsó korláttal és megoldjuk a z = célfüggvény segítségével.
| 1/c Írja be a fenti számokat a megfelelő helyre! Súlyozási módszer: Egy -t állítunk elő a két -ből úgy, hogy mindkét célfüggvényt egy alkalmas súllyal és a szorzatokat . Ez lesz az új .
| 2. Egy kétcélú programozási feladatot oldottunk meg szimplex módszerrel és a következő táblázatot kaptuk:
| Értékelje a táblázatot, majd döntse el, hogy az alábbi állítások igazak vagy hamisak!
A B2-es táblázatban a z2 szerint nem optimális a táblázatban látható megoldás. |
A B2-es táblázatban a z1 szerint optimális megoldás látható. |
A B2-es táblázatban látszik, hogy a z1 célfüggvény szerint alternatív optimum van. |
A B2-es táblázatban látszik, hogy a z2 célfüggvény nem korlátos. |
| 3. Olvasson le vagy állítson elő egy Pareto-optimális megoldást, ha létezik. Vegyen elő egy lapot és számoljon.
| Eredményt írja ebbe a táblázatba! A B3 táblázat így néz ki:
B 3 | u 1 | u 2 |
x 1 |  |  |
u 3 |  |  |
x 2 |  |  |
+ z 1 |  |  |
− z 2 |  |  |
| Értékelje az eredményt, majd döntse el, hogy az alábbi állítások igazak vagy hamisak!
A B 3 -as táblázatban csak a z 2 szerint optimális megoldás látható. |
A B 3 -as táblázatban mindkét célfüggvény szerint optimális a megoldás látható. |
A feladatnak nincs olyan megoldása, amely mindkét célfüggvény szerint optimális megoldás lenne. |
| 4. Ha talált optimális megoldást, azt írja ide! x 1 = x 2 = z 1 = z 2 =
| 5. Oldja meg Solver segítségével a következő többcélú programozási feladatot a célfüggvények súlyozási módszerével!
| 2 x 1 + x 2 ≤ 80 x 1 +2 x 2 ≤ 60 x 1 ≤ 30 z 1 =30 x 1 +40 x 2 → max⁡ z 2 =20 x 1 +50 x 2 → max⁡
| Az első célfüggvény súlya 70%, a másodiké pedig 30% legyen.
| 5/a Mik lesznek az egyetlen célfüggvény együtthatói? Írja be az értékeket a megfelelő helyre! z = x 1 + x 2 → max⁡
| 5/b Írja be a fenti feladat optimális megoldásának elemeit a megfelelő helyre! x 1 = x 2 = z = z 1 = z 2 =